package fun.codedesign.jdk.math.algorithm.sort;

/**
 * 桶排序 <br>
 * <pre>
 *     桶排序的采用分治的思想，将数据分配到有限数量的桶中，再在桶中完成排序，需要的时候再取出
 *     类似 数组+链表 实现的HashMap
 *     TODO 此处的桶排序存在问题
 * </pre>
 *
 * @author zengjian
 * @create 2018-06-27 17:02
 * @since 1.0.0
 */
public class BucketSorter implements Sorter {
    @Override
    public void sort(int[] arr) {
        int length = arr.length;
        int bask[][] = new int[10][length];
        int count[] = new int[10];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            max = Math.max(max, Integer.toString(arr[i]).length());
        }
        String str;
        for (int i = max - 1; i >= 0; i--) {
            for (int j = 0; j < length; j++) {
                // 不足位数的在前面补0
                str = "";
                String a = Integer.toString(arr[j]);
                if (a.length() < max) {
                    for (int k = 0; k < max - a.length(); k++) {
                        str += "0";
                    }
                }
                str += a;
                // 此处与基数排序一样
                bask[str.charAt(i) - '0'][count[str.charAt(i) - '0']++] = arr[j];
            }
            int pos = 0;
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < count[j]; k++) {
                    arr[pos++] = bask[j][k];
                }
                count[j] = 0;
            }
        }
    }

    /**
     * 修正方法，桶的个数设置与数组长度关联，而桶的内部数据结构可以分为小数组或者其他
     * @param arr
     */
    public void bucketSort(int[] arr){
        /**
         * 先将arr的最大值和最小值取出
         */


    }
}